/**
 * 希尔排序
 * 算法思路：将数组分为若干h个小组(一般为 length/2)，然后对每个小组分别进行插入排序，每轮分割数组逐步缩小：h/2->h/4->h/8，且排序，知道h为1，数组排序完成
 * 算法时间复杂度：O(n2)
 * 算法空间复杂度：O(1)
 */

export default function (pararr) {
    if (!Array.isArray(pararr) || pararr.length < 2) {
        return;
    }
    let arr = [].concat(pararr);
    // @todo 数组个数是奇数还是偶数需要考虑下
    // 每间隔 n 的数需要做插入排序
    let gap = arr.length/2;
    while(gap>=1){
        //内部插入排序
        for(let i = 0;i<arr.length-1;i++){
            //表示最小值的索引起始位置
            let idx = i;
            for(let j = i+1;j<=arr.length-1;j++){
                if(arr[idx]>arr[j]){
                    idx = j;
                }
            }
            //移动最小的元素
            arr.splice(i,0,arr.splice(idx,1)[0]);
        }
        gap/=2;
    }
    return arr;
}